# bucket_sort.py


# 桶排序 n表示桶的个数 是计数排序的升级版 - 不需要一次性开辟max_value+1个空间长度
def bucket_sort(data, n=100, max_value=10000):
    buckets = [[] for _ in range(n)]  # n个小桶

    for val in data:
        # i表示桶的编号，范围为: 0 - 99
        # 每个桶最多容纳元素的个数max_value // n
        # min确保10000落在最后一个桶中(99号)
        i = min(val // (max_value // n), n-1)
        buckets[i].append(val)

        # 维护桶中元素的顺序
        # 1 4 5 2
        #       j (len(bucket[i])-1)
        for j in range(len(buckets[i])-1, 0, -1):
            if buckets[i][j] < buckets[i][j-1]:
                buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
            else:
                break
    
    # 这时buckets中的每个桶都拍好了序
    return [val for bucket in buckets for val in bucket]


import random
data = [random.randint(0, 10000) for _ in range(1000)]
result = bucket_sort(data)
print(result)